home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / graphics.swg / 0107_Fast Polygons.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1994-08-24  |  13.4 KB  |  424 lines
  1. {
  2. This unit draws polygons fast. It draws only polygons which are monotone
  3. vertical. That means only polygons which you can fill with continues horizontal
  4. lines. Fortunately that are the polygons which are mostly used in 3d graphics.
  5. }
  6.  
  7. {*****************************************************************}
  8. {* UnitName    : FASTPOLY.PAS                                    *}
  9. {* Purpose     : Draw monotone vertical polygons fast            *}
  10. {* Version     : 1.5                                             *}
  11. {* Author      : Daan de Haas                                    *}
  12. {* Date        : 20/10/1993                                      *}
  13. {* Last update :  9/06/1994                                      *}
  14. {* Language    : Borland Turbo Pascal 7.0                        *}
  15. {* Fidonet     : Daan de Haas (2:500/104.6141)                   *}
  16. {* Internet    : Daan.de.Haas@p6141.f104.n500.z2.fidonet.org     *}
  17. {*****************************************************************}
  18.  
  19. {* VGA mode $13 and 386 processor *}
  20. {* Literatur : Dr Dobb's XSharp   *}
  21.  
  22. {$R-,S-,Q-,I-}
  23.  
  24. UNIT FastPoly;
  25.  
  26. {**************************} INTERFACE {**************************}
  27.  
  28. TYPE
  29.   PPoint = ^TPoint;
  30.   TPoint = RECORD
  31.              x,y:integer;
  32.            END;
  33.   PPolygon = ^TPolygon;
  34.   PPointsList = ^TPointsList;
  35.   TPointsList = ARRAY[0..9999] OF TPoint;
  36.   TPolygon = RECORD
  37.                length,color:word;
  38.                PointPtr:PPointsList;
  39.              END;
  40.   PHLine = ^THLine;
  41.   THLine = RECORD
  42.              XStart,XEnd:word;
  43.            END;
  44.   PHLineArray = ^THLineArray;
  45.   THLineArray = ARRAY[0..9999] OF THLine;
  46.   THLineList = RECORD
  47.                  length,YStart:integer;
  48.                  HLinePtr : PHLineArray;
  49.                END;
  50.  
  51. PROCEDURE HLine(x1,y1,x2:word; color:word);
  52. PROCEDURE InitPoly(VAR p:TPolygon; len,col:word);
  53. PROCEDURE DonePoly(VAR p:TPolygon);
  54. PROCEDURE FillMonotoneVerticalPolygon(XOffset,YOffset:word;
  55.                                       VertexList:TPolygon);
  56.  
  57. CONST
  58.   MaxX=320;
  59.   MaxY=200;
  60.   VidSegment=$A000;
  61.  
  62. {************************} IMPLEMENTATION {***********************}
  63.  
  64. PROCEDURE HLine; ASSEMBLER;
  65. ASM
  66.   mov ax,x1             { x1 < x2 }
  67.   cmp ax,x2
  68.   jl  @@skip1
  69.   je  @@lijnexit
  70.   xchg ax,x2
  71.   mov  x1,ax
  72. @@skip1:
  73.   mov ax,maxX           { calculate y1*maxX+x1 }
  74.   mul y1
  75.   add ax,x1
  76. @@1:
  77.   mov di,ax             { dx=segment, di=offset }
  78.   mov ax,VidSegment
  79.  
  80. @@skip2:
  81.   cld                   { forward direction }
  82.   mov cx,x2
  83.   sub cx,x1
  84.   inc cx                { cx = number of pixels in line }
  85.   mov dx,di
  86.   add dx,cx
  87.   mov es,ax             { load segment register }
  88.   mov ax,color          { get color into 386 register eax }
  89.   mov ah,al
  90.   mov dx,ax
  91.   db  $66,$c1,$e0,$10   { shl eax,16 (386 code) }
  92.   mov ax,dx
  93.   test di,00000011b
  94.   jz @@skip             { test for doubleword border, if so jump }
  95. @@waitdd:
  96.   mov  es:[di],al       { put one pixel }
  97.   inc  di               { di:=next pixel address }
  98.   test di,00000011b     { doubleword border  ? }
  99.   loopnz @@waitdd       { stop if cx=0 or zeroflag 1 }
  100.   or  cx,cx             { cx=0 ? }
  101.   jz  @@lijnexit        { if so, line is ready }
  102.   cmp cx,4              { is a stosd possible ? }
  103.   jl  @@waitdd          { no, then pixel after pixel }
  104. @@skip:
  105.   mov  dx,cx
  106.   shr  cx,2
  107.   db   $f3,$66,$AB      { rep stosd (386 code) }
  108.   mov  cx,dx
  109.   and cx,00000011b      { line finished ? }
  110.   jnz @@waitdd
  111. @@lijnexit:
  112. END;
  113.  
  114. PROCEDURE ScanEdge(x1,y1,x2,y2,SetXStart,SkipFirst:integer;
  115.                    VAR EdgePointPtr:PHLineArray); ASSEMBLER;
  116. { Scan converts an edge from (X1,Y1) to (X2,Y2), not including the
  117.  point at (X2,Y2). If SkipFirst == 1, the point at (X1,Y1) isn't
  118.  drawn; if SkipFirst == 0, it is. For each scan line, the pixel
  119.  closest to the scanned edge without being to the left of the scanned
  120.  edge is chosen. Uses an all-integer approach for speed & precision.
  121.  
  122.  Edges must not go bottom to top; that is, Y1 must be <= Y2.
  123.  Updates the pointer pointed to by EdgePointPtr to point to the next
  124.  free entry in the array of HLine structures. }
  125.  
  126. VAR
  127.   AdvanceAmt,Height:word;
  128.  
  129. ASM
  130.  les di,EdgePointPtr
  131.  les di,es:[di]  { point to the HLine array }
  132.  cmp SetXStart,1      { set the XStart field of each HLine
  133.      { struc? }
  134.  jz @@HLinePtrSet  { yes, DI points to the first XStart }
  135.  add di,2   { no, point to the XEnd field of the }
  136.      {  first HLine struc }
  137. @@HLinePtrSet:
  138.  mov bx,Y2
  139.  sub bx,Y1         { edge height }
  140.  jle @@ToScanEdgeExit{ guard against 0-length & horz edges }
  141.  mov Height,bx { Height = Y2 - Y1 }
  142.  sub cx,cx  { assume ErrorTerm starts at 0 (true if }
  143.                                 {  we're moving right as we draw) }
  144.  mov dx,1  { assume AdvanceAmt = 1 (move right) }
  145.  mov ax,X2
  146.  sub ax,X1           { DeltaX = X2 - X1 }
  147.         jz      @@IsVertical   { it's a vertical edge--special case it }
  148.  jns @@SetAdvanceAmt { DeltaX >= 0 }
  149.  mov cx,1  { DeltaX < 0 (move left as we draw) }
  150.  sub cx,bx  { ErrorTerm = -Height + 1 }
  151.  neg dx  { AdvanceAmt = -1 (move left) }
  152.         neg     ax              { Width = abs(DeltaX) }
  153. @@SetAdvanceAmt:
  154.  mov AdvanceAmt,dx
  155. { Figure out whether the edge is diagonal, X-major (more horizontal), }
  156. { or Y-major (more vertical) and handle appropriately. }
  157.  cmp ax,bx  { if Width==Height, it's a diagonal edge }
  158.  jz @@IsDiagonal { it's a diagonal edge--special case }
  159.  jb @@YMajor { it's a Y-major (more vertical) edge }
  160.     { it's an X-major (more horz) edge }
  161.         sub     dx,dx           { prepare DX:AX (Width) for division }
  162.         div     bx  { Width/Height }
  163.     { DX = error term advance per scan line }
  164.  mov si,ax  { SI = minimum # of pixels to advance X }
  165.     { on each scan line }
  166.         test    AdvanceAmt,8000h { move left or right? }
  167.         jz      @@XMajorAdvanceAmtSet   { right, already set }
  168.         neg     si              { left, negate the distance to advance }
  169.     { on each scan line }
  170. @@XMajorAdvanceAmtSet:
  171.  mov ax,X1  { starting X coordinate }
  172.         cmp     SkipFirst,1 { skip the first point? }
  173.         jz @@XMajorSkipEntry  { yes }
  174. @@XMajorLoop:
  175.  mov es:[di],ax  { store the current X value }
  176.  add di,4     { point to the next HLine struc }
  177. @@XMajorSkipEntry:
  178.  add ax,si  { set X for the next scan line }
  179.  add cx,dx  { advance error term }
  180.  jle @@XMajorNoAdvance { not time for X coord to advance one }
  181.     { extra }
  182.  add ax,AdvanceAmt { advance X coord one extra }
  183.         sub     cx,Height     { adjust error term back }
  184. @@XMajorNoAdvance:
  185.         dec     bx  { count off this scan line }
  186.         jnz     @@XMajorLoop
  187.  jmp @@ScanEdgeDone
  188. @@ToScanEdgeExit:
  189.  jmp @@ScanEdgeExit
  190. @@IsVertical:
  191.  mov ax,X1 { starting (and only) X coordinate }
  192.  sub bx,SkipFirst { loop count = Height - SkipFirst }
  193.         jz      @@ScanEdgeExit  { no scan lines left after skipping 1st }
  194. @@VerticalLoop:
  195.  mov es:[di],ax  { store the current X value }
  196.  add di,4 { point to the next HLine struc }
  197.  dec bx  { count off this scan line }
  198.  jnz @@VerticalLoop
  199.  jmp @@ScanEdgeDone
  200. @@IsDiagonal:
  201.  mov ax,X1 { starting X coordinate }
  202.         cmp     SkipFirst,1 { skip the first point? }
  203.  jz @@DiagonalSkipEntry { yes }
  204. @@DiagonalLoop:
  205.  mov es:[di],ax  { store the current X value }
  206.  add di,4 { point to the next HLine struc }
  207. @@DiagonalSkipEntry:
  208.  add ax,dx  { advance the X coordinate }
  209.  dec bx  { count off this scan line }
  210.  jnz @@DiagonalLoop
  211.  jmp @@ScanEdgeDone
  212.  
  213. @@YMajor:
  214.  push bp { preserve stack frame pointer }
  215.  mov si,X1  { starting X coordinate }
  216.         cmp     SkipFirst,1 { skip the first point? }
  217.  mov bp,bx { put Height in BP for error term calcs }
  218.         jz @@YMajorSkipEntry { yes, skip the first point }
  219. @@YMajorLoop:
  220.  mov es:[di],si { store the current X value }
  221.  add di,4 { point to the next HLine struc }
  222. @@YMajorSkipEntry:
  223.  add cx,ax  { advance the error term }
  224.  jle @@YMajorNoAdvance { not time for X coord to advance }
  225.  add si,dx  { advance the X coordinate }
  226.         sub     cx,bp  { adjust error term back }
  227. @@YMajorNoAdvance:
  228.         dec     bx  { count off this scan line }
  229.         jnz     @@YMajorLoop
  230.  pop bp  { restore stack frame pointer }
  231. @@ScanEdgeDone:
  232.  cmp SetXStart,1 { were we working with XStart field? }
  233.  jz @@UpdateHLinePtr { yes, DI points to the next XStart  }
  234.  sub di,2  { no, point back to the XStart field }
  235. @@UpdateHLinePtr:
  236.         mov     bx,word ptr EdgePointPtr { point to pointer to HLine array }
  237.  mov ss:[bx],di  { update caller's HLine array pointer }
  238. @@ScanEdgeExit:
  239. END;
  240.  
  241. PROCEDURE DrawHorizontalLineList(VAR list:THLineList; color:word); ASSEMBLER;
  242. ASM
  243.   les si,list
  244.   mov cx,es:[si]                { cx = number of lines }
  245.   mov ax,es:[si+2]              { ax = startY }
  246.   les si,es:[si+4]              { es:si points to pointlist }
  247. @@loop:
  248.   mov bx,es:[si]                { get startX }
  249.   mov dx,es:[si+2]              { get endX }
  250.   push cx                       { save registers }
  251.   push ax
  252.   push si
  253.   push es
  254.  
  255.   push bx                       { draw horizontal line }
  256.   push ax
  257.   push dx
  258.   mov  dx,color                 { get color }
  259.   push dx
  260.   call HLine
  261.  
  262.   pop es                        { restore registers }
  263.   pop si
  264.   pop ax
  265.   pop cx
  266.   inc ax                        { y:=y+1 }
  267.   add si,4                      { next points }
  268.   loop @@loop                   { if length=0 then stop }
  269. END;
  270.  
  271. PROCEDURE FillMonotoneVerticalPolygon;
  272. VAR
  273.   i,MinIndex,MaxIndex,MinPoint_y,MaxPoint_y,NextIndex,
  274.   CurrentIndex,PreviousIndex:integer;
  275.   WorkingHLineList:THLineList;
  276.   EdgePointPtr:PHLineArray;
  277.   VertexPtr:PPointsList;
  278. BEGIN
  279.   IF VertexList.Length=0 THEN Exit;
  280.   VertexPtr:=VertexList.PointPtr;
  281.   MaxPoint_y:=VertexPtr^[0].y;
  282.   MinPoint_y:=MaxPoint_y;
  283.   MinIndex:=0;
  284.   MaxIndex:=0;
  285.   FOR i:=1 TO VertexList.Length-1 DO
  286.     WITH VerTexPtr^[i] DO
  287.       IF y<MinPoint_y THEN
  288.         BEGIN
  289.           MinPoint_y:=y;
  290.           MinIndex:=i;
  291.         END
  292.       ELSE
  293.         IF y>MaxPoint_y THEN
  294.           BEGIN
  295.             MaxPoint_y:=y;
  296.             MaxIndex:=i;
  297.           END;
  298.   WITH WorkingHLineList DO
  299.     BEGIN
  300.       length:=MaxPoint_y-MinPoint_y;
  301.       IF length<=0 THEN Exit;
  302.       YStart:=YOffset+MinPoint_y;
  303.       GetMem(HLinePtr,SizeOf(THLine)*length);
  304.       EdgePointPtr:=HLinePtr;
  305.     END;
  306.   CurrentIndex:=MinIndex;
  307.   PreviousIndex:=MinIndex;
  308.   REPEAT
  309.     CurrentIndex:=(CurrentIndex+VertexList.length-1) MOD VertexList.length;
  310.     ScanEdge(VertexPtr^[PreviousIndex].x+XOffset,
  311.              VertexPtr^[PreviousIndex].y,
  312.              VertexPtr^[CurrentIndex].x+XOffset,
  313.              VertexPtr^[CurrentIndex].y,
  314.              1,0,EdgePointPtr);
  315.     PreviousIndex:=CurrentIndex;
  316.   UNTIL CurrentIndex=MaxIndex;
  317.   EdgePointPtr:=WorkingHLineList.HLinePtr;
  318.   CurrentIndex:=MinIndex;
  319.   PreviousIndex:=MinIndex;
  320.   REPEAT
  321.     CurrentIndex:=(CurrentIndex+1) MOD VertexList.length;
  322.     ScanEdge(VertexPtr^[PreviousIndex].x+XOffset,
  323.              VertexPtr^[PreviousIndex].y,
  324.              VertexPtr^[CurrentIndex].x+XOffset,
  325.              VertexPtr^[CurrentIndex].y,
  326.              0,0,EdgePointPtr);
  327.     PreviousIndex:=CurrentIndex;
  328.   UNTIL CurrentIndex=MaxIndex;
  329.   DrawHorizontalLineList(WorkingHLineList,VertexList.color);
  330.   WITH WorkingHLineList DO FreeMem(HLinePtr,SizeOf(THLine)*length);
  331. END;
  332.  
  333. PROCEDURE InitPoly;
  334. BEGIN
  335.   WITH p DO
  336.     BEGIN
  337.       length:=len;
  338.       color:=col;
  339.       { No Error checking !}
  340.       GetMem(PointPtr,len*SizeOf(TPoint));
  341.     END;
  342. END;
  343.  
  344. PROCEDURE DonePoly;
  345. BEGIN
  346.   WITH p DO
  347.     BEGIN
  348.       IF PointPtr<>NIL THEN FreeMem(PointPtr,length*SizeOf(TPoint));
  349.       PointPtr:=NIL;
  350.     END;
  351. END;
  352.  
  353. END.
  354.  
  355. {*****************************************************************}
  356. {* ProgramName : FASTPOL.PAS                                     *}
  357. {* Purpose     : Demonstration of unit FastPoly                  *}
  358. {* Version     : 1.0                                             *}
  359. {* Author      : Daan de Haas                                    *}
  360. {* Date        : 9 jun 1994                                      *}
  361. {* Last update : 9 jun 1994                                      *}
  362. {* Language    : Borland Pascal 7.0                              *}
  363. {* Fidonet     : Daan de Haas (2:500/104.6141)                   *}
  364. {* Internet    : Daan.de.Haas@p6141.f104.n500.z2.fidonet.org     *}
  365. {*****************************************************************}
  366.  
  367. {$R-,I-,Q-,S-}
  368.  
  369. USES
  370.   Crt, FastPoly;
  371.  
  372. PROCEDURE SetVideo(m:word); ASSEMBLER;
  373. ASM
  374.   mov ax,m
  375.   int $10
  376. END;
  377.  
  378. PROCEDURE Polydemo;
  379. VAR
  380.   p1,p2:TPolygon;
  381. BEGIN
  382.   InitPoly(p1,6,YELLOW);
  383.   p1.PointPtr^[0].X:=10;
  384.   p1.PointPtr^[0].Y:=0;
  385.   p1.PointPtr^[1].X:=20;
  386.   p1.PointPtr^[1].Y:=0;
  387.   p1.PointPtr^[2].X:=30;
  388.   p1.PointPtr^[2].Y:=10;
  389.   p1.PointPtr^[3].X:=20;
  390.   p1.PointPtr^[3].Y:=20;
  391.   p1.PointPtr^[4].X:=10;
  392.   p1.PointPtr^[4].Y:=20;
  393.   p1.PointPtr^[5].X:=0;
  394.   p1.PointPtr^[5].Y:=10;
  395.   InitPoly(p2,6,BLUE);
  396.   p2.PointPtr^[0].X:=10;
  397.   p2.PointPtr^[0].Y:=0;
  398.   p2.PointPtr^[1].X:=20;
  399.   p2.PointPtr^[1].Y:=0;
  400.   p2.PointPtr^[2].X:=30;
  401.   p2.PointPtr^[2].Y:=10;
  402.   p2.PointPtr^[3].X:=20;
  403.   p2.PointPtr^[3].Y:=20;
  404.   p2.PointPtr^[4].X:=10;
  405.   p2.PointPtr^[4].Y:=20;
  406.   p2.PointPtr^[5].X:=0;
  407.   p2.PointPtr^[5].Y:=10;
  408.   REPEAT
  409.     FillMonotoneVerticalPolygon(Random(MaxX-35),Random(MaxY-25),p1);
  410.     FillMonotoneVerticalPolygon(Random(MaxX-35),Random(MaxY-25),p2);
  411.   UNTIL KeyPressed;
  412.   ReadKey;
  413.   DonePoly(p1);
  414.   DonePoly(p2);
  415. END;
  416.  
  417. BEGIN
  418.   ClrScr;
  419.   Randomize;
  420.   SetVideo($13);
  421.   PolyDemo;
  422.   SetVideo(3);
  423. END.
  424.